package com.hejing.排序算法;

import java.text.SimpleDateFormat;
import java.util.Date;

public class RadixSort {
    public static void main(String[] args) {
        // int[] arr = {1, -1, 90, 31, 922, -102, 0, 221, 441, -100};

        int count = 8000000;
        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = (int)(Math.random() *  10000000);
        }

        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Date date1 = new Date();
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("排序前的时间: " + date1Str);
        // System.out.println("排序前的数组: " + Arrays.toString(arr));

        radixSort(arr);

        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("排序后的时间:" + date2Str);
        // System.out.println("排序后的数组: " + Arrays.toString(arr));

    }

    /**
     * 基数排序
     * 基数排序无法对负数进行排序，此处采用数组中所有的元素 都加上一个最小数(为负数，若最小数为正数，不进行
     * 此操作)的绝对值。后续再统一减去此数。
     * @param arr 待排序数组
     */
    public static void radixSort(int[] arr) {

        // 解决负数排序的情况:
        // 1、求出序列中的最小值
        int minVal = getArrayMin(arr);
        // 2、如果待排序数组的最小值是一个负数，则将数组中每一个元素都统一加上一个该最小值的绝对值，
        // 如果最小值是一个非负数，则不用管。
        if (minVal < 0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] += Math.abs(minVal);
            }
        }

        // 求取出待排序数组中的最大的数的位数
        int maxArrVal = getArrayMax(arr);
        int digits = (maxArrVal + "").length();

        // 定义10个桶，每个桶的最大容量是待排序数组的长度
        int[][] bucket= new int[10][arr.length];

        // 因为我们针对不同的位数在每一轮都会在桶中保存数据，为了方便进行逻辑上的擦除重写，
        // 我们定义一个实时保存每个桶中的数据个数的数组，在每一轮(处理不同位数)结束前，先
        // 将该数组的元素置零，在下一轮保存数据时直接从下标0开始，进行重写操作，这边是逻辑上的删除。
        int[] bucketElementCounts = new int[arr.length];

        for (int digit = 0; digit < digits; digit++) {
            int index = 0;  // 索引，
            for (int j = 0; j < arr.length; j++) {  // 遍历每一个元素
                // 针对不同的位数i, 分别求出每个数的个位/十位/百位...
                int digitOfElement = arr[j] / (int)Math.pow(10, digit) % 10;
                // 将每个位数所在的数保存到桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j];
            }
            // 将桶中的数据一一保存到数组中。
            for (int k = 0; k < bucket.length; k++) {
                // 桶中有数据才进行保存操作
                if (bucketElementCounts[k] > 0) {
                    for(int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                    // 每一轮结束前，将保存各个桶的元素信息的bucketElementCounts数组置零
                    bucketElementCounts[k] = 0;
                }
            }
        }

        // 判断，如果原数组最小值是一个负数，则处理过的数组所有元素均需要减去一个最小值的绝对值
        if (minVal < 0) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] -= Math.abs(minVal);
            }
        }
    }

    /**
     * 求出序列中的最大值
     * @param arr
     * @return
     */
    public static int getArrayMax(int[] arr) {
        if (arr.length < 1) {
            throw new RuntimeException("数组为空，无法求出最大值");
        } else if(arr.length == 1) {
            return arr[0];
        } else {
            int maxVal = arr[0];
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > maxVal) {
                    maxVal = arr[i];
                }
            }
            return maxVal;
        }
    }

    /**
     * 求出序列中的最小值
     * @param arr
     * @return
     */
    public static int getArrayMin(int[] arr) {
        if (arr.length < 1) {
            throw new RuntimeException("数组为空，无法求取最小值");
        } else if(arr.length == 1) {
            return arr[0];
        } else {
            int minVal = arr[0];
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] < minVal) {
                    minVal = arr[i];
                }
            }
            return minVal;
        }
    }
}
























